package org.chnxi.algorithm.kruskal;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;

/**
 * 最小生成树-克鲁斯卡尔算法
 */
public class KruskalAlgorithm {

    //记录边的个数
    private int edgeNum;
    //存放顶点的数组
    private char[] vertexs;
    //邻接矩阵
    private int[][] matrix;
    //表示不连通的两个顶点
    static final int INF = Integer.MAX_VALUE;

    public static void main(String[] args) {

        char[] vertexs = {'A','B','C','D','E','F','G'};

        int[][] matrix = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };

        KruskalAlgorithm ka = new KruskalAlgorithm(vertexs , matrix);
        System.out.println("使用克鲁斯卡尔的算法：");
        ka.kruskal();
    }

    public KruskalAlgorithm(char[] vertexs, int[][] matrix){
        //初始化顶点和边的个数
        int vlen = vertexs.length;

        //初始化顶点，将数据拷贝过来
        this.vertexs = new char[vlen];
        for(int i=0;i<vlen;i++){
            this.vertexs[i] = vertexs[i];
        }

        //初始化边，将数据copy过来
        this.matrix = new int[vlen][vlen];
        for (int i=0;i<vlen;i++){
            for (int j=0;j<vlen;j++){
                this.matrix[i][j] = matrix[i][j];
            }
        }

        //统计有多少条边
        for (int i=0;i<vlen;i++){
            for (int j=i+1;j<vlen;j++){
                if(this.matrix[i][j] != INF){
                    edgeNum++;
                }
            }
        }

    }

    /**
     * 打印邻接矩阵
     */
    public void print(){
        for (int i=0;i<vertexs.length;i++){
            for (int j=0;j<vertexs.length;j++){
                System.out.printf("%11d",matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 对边进行冒泡排序
     * @param edges 边的集合
     */
    private void sortEdges(EData[] edges){
        for(int i=0;i<edges.length -1;i++){
            for (int j =0;j<edges.length -1;j++){
                if(edges[j].weight > edges[j+1].weight){
                    EData tmp = edges[j];
                    edges[j] = edges[j+1];
                    edges[j+1] = tmp;
                }
            }
        }
    }

    /**
     * 查找顶点对应的下标
     * @param ch 顶点的值
     * @return 返回顶点对应的下标，找不到返回-1
     */
    private int getPosition(char ch){
        for (int i=0; i< vertexs.length;i++){
            if(vertexs[i] == ch){
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取途中的边，放到EData[]中，便于遍历
     * 通过matrix邻接矩阵获取
     * EData[] = { EData:{'A','B',12},.... }
     * @return
     */
    private EData[] getEdges(){
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i=0; i< vertexs.length;i++){
            for (int j=i+1; j< vertexs.length;j++){
                if(matrix[i][j] != INF){
                    edges[index++] = new EData(vertexs[i] , vertexs[j] , matrix[i][j]);
                }
            }
        }
        return edges;
    }

    /**
     * 获取下标为i的顶点的终点
     * @param ends 数组是记录了各个顶点对应的终点是哪个，数组在遍历过程中逐步形成的
     * @param i 表示传入的顶点对应的下标
     * @return 返回的就是下标为i的这个顶点对应的终点的下标
     */
    private int getEnd(int[] ends , int i){
        while (ends[i] != 0){
            i = ends[i];
        }
        return i;
    }

    /**
     * 使用克鲁斯卡尔算法生成最小树
     */
    public void kruskal(){
        int index = 0; //表示最后结果数组的索引
        int[] ends = new int[edgeNum]; //用于保存已有最小生成树中的每个顶点在最小生成树中的重点
        EData[] result = new EData[edgeNum];//创建结果数组，保存最后的最小生成树

        //获取图中所有边的集合
        EData[] edges = getEdges();

        //按照边的大小进行排序（从下到大）
        this.sortEdges(edges);

        //遍历edges，将边添加到最小生成树中时，判断是准备加入的边是否形成了回路，如果没有，就加入到result中，否则不能加入
        for(int i=0; i<edgeNum; i++){
            //获取到第条边的第一个顶点(起点）
            int p1 = getPosition(edges[i].start);
            //获取到第i条边的第2个顶点
            int p2 = getPosition(edges[i].end);

            //获取p1这个顶点在有最小生成树中的重点；
            int m = getEnd(ends , p1);
            //获取p2这个顶点在有最小生成树中的重点；
            int n = getEnd(ends , p2);

            if(m != n){
                ends[m] = n; //设置m在已有最小生成树中的终点
                result[index++] = edges[i]; //符合规则的边加入到result中
            }
        }

        System.out.println("最小生成树："+Arrays.toString(result));
    }
}

//创建一个类EData，它的对象实例表示一条边
@Data
@AllArgsConstructor
@NoArgsConstructor
class EData{
    char start; //边的一个顶点
    char end; //边的另外一个订单
    int weight;//边的权值

}
